package com.lfg.leetcode.leetcode200;

public class No221maximalSquare {

    public static void main(String[] args) {
        int ret = maximalSquare(new char[][]{
                new char[]{'1', '1', '1', '1', '0'},
                new char[]{'1', '1', '1', '1', '1'},
                new char[]{'1', '1', '1', '0', '1'},
                new char[]{'1', '1', '1', '1', '1'},
        });
        System.out.println(ret);
    }

    public static int maximalSquare(char[][] matrix) {
        int ret = 0;

        if (matrix.length == 0) {
            return ret;
        }

        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dp = new int[m][n];
        for (int y = 0; y < matrix.length; y++) {
            if (matrix[y][0] == '1') {
                dp[y][0] = 1;
                ret = 1;
            }
        }
        for (int x = 0; x < n; x++) {
            if (matrix[0][x] == '1') {
                dp[0][x] = 1;
                ret = 1;
            }
        }

        for (int y = 1; y < m; y++) {
            for (int x = 1; x < n; x++) {

                if (matrix[y][x] == '1') {
                    dp[y][x] = Math.min(Math.min(dp[y][x - 1], dp[y - 1][x]), dp[y - 1][x - 1]) + 1;
                }
                ret = Math.max(ret, dp[y][x]);
            }
        }

        return ret * ret;
    }
}
